#include<bits/stdc++.h>
#define N 1100000
#define db double
#define ll long long
#define ldb long double
#define ull unsigned long long
using namespace std;
const int pr=3,ki=149,inf=1e9+7,mo=998244353;
inline int neg(int x){return x?mo-x:0;}
inline int mod(int x){return (x%mo+mo)%mo;}
inline int inc(int x,int k){x+=k;return x<mo?x:x-mo;}
inline int dec(int x,int k){x-=k;return x>=0?x:x+mo;}
inline int ksm(int x,int k)
{
	int ans=1;
	while(k){if(k&1)ans=1ll*ans*x%mo;k>>=1;x=1ll*x*x%mo;}
	return ans;
}
inline int inv(int x){return ksm(x,mo-2);}
inline int read()
{
	char ch=0;int x=0,flag=1;
	while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0',ch=getchar();}
	return x*flag;
}
inline void write(int x)
{
	if(!x)return (void)putchar(48);
	if(x<0)putchar(45),x=-x;
	int len=0,p[20];
	while(x)p[++len]=x%10,x/=10;
	for(int i=len;i>=1;i--)putchar(p[i]+48);
}
inline void writeln(int x){write(x);putchar('\n');}
int rev[N];
void ntt(int *f,int n,int flag)
{
	for(int i=0;i<n;i++)
	{
		rev[i]=(rev[i>>1]>>1)+(i&1)*(n>>1);
		if(i<rev[i])swap(f[i],f[rev[i]]);
	}
	for(int k=2,kk=1;k<=n;k<<=1,kk<<=1)
	{
		int wn=ksm(pr,(mo-1)/k);
		if(flag==-1)wn=inv(wn);
		for(int i=0;i<n;i+=k)
		for(int j=0,w=1;j<kk;j++,w=1ll*w*wn%mo)
		{
			int t=1ll*w*f[i+j+kk]%mo;
			f[i+j+kk]=dec(f[i+j],t);f[i+j]=inc(f[i+j],t);
		}
	}
	if(flag==-1)
	{
		int k=inv(n);
		for(int i=0;i<n;i++)f[i]=1ll*f[i]*k%mo;
	}
}
int a[N],b[N];
void poly_ml(int n)
{
	int len=1;while(len<2*n-1)len<<=1;
	for(int i=n;i<len;i++)a[i]=0;
	ntt(a,len,+1);
	for(int i=0;i<len;i++)a[i]=1ll*a[i]*a[i]%mo;
	ntt(a,len,-1);
}
void poly_mul(int n,int m)
{
	int len=1;while(len<n+m-1)len<<=1;
	for(int i=n;i<len;i++)a[i]=0;
	for(int i=m;i<len;i++)b[i]=0;
	ntt(a,len,+1);ntt(b,len,+1);
	for(int i=0;i<len;i++)a[i]=1ll*a[i]*b[i]%mo;
	ntt(a,len,-1);
}
int fv[N],gv[N];
void poly_inv(int n)
{
	for(int i=0;i<n;i++)fv[i+n]=gv[i]=gv[i+n]=0;
	int len=1;gv[0]=inv(fv[0]);
	while(len<n)
	{
		len<<=1;
		for(int i=0;i<len;i++)a[i]=gv[i];poly_ml(len);
		for(int i=0;i<len;i++)b[i]=fv[i];poly_mul(len,len);
		for(int i=0;i<len;i++)gv[i]=dec(2ll*gv[i]%mo,a[i]);
	}
	for(int i=0;i<n;i++)gv[i+n]=fv[i]=fv[i+n]=0;
}
int fs[N],gs[N];
void poly_sqrt(int n)
{
	for(int i=0;i<n;i++)fs[i+n]=gs[i]=gs[i+n]=0;
	int len=1;gs[0]=sqrt(fs[0]);
	while(len<n)
	{
		len<<=1;
		for(int i=0;i<len;i++)fv[i]=2ll*gs[i]%mo;poly_inv(len);
		for(int i=0;i<len;i++)a[i]=gs[i];poly_ml(len);
		for(int i=0;i<len;i++)a[i]=inc(fs[i],a[i]),b[i]=gv[i];poly_mul(len,len);
		for(int i=0;i<len;i++)gs[i]=a[i];
	}
	for(int i=0;i<n;i++)gs[i+n]=fs[i]=fs[i+n]=0;
}

int fd[N],gd[N];
void poly_der(int n)
{
	for(int i=0;i<2*(n+1);i++)gd[i]=0;
	for(int i=0;i<n-1;i++)gd[i]=1ll*(i+1)*fd[i+1]%mo;
	for(int i=0;i<n;i++)fd[i]=0;
}
int fi[N],gi[N];
void poly_int(int n)
{
	for(int i=0;i<2*(n+1);i++)gi[i]=0;
	for(int i=1;i<n+1;i++)gi[i]=1ll*inv(i)*fi[i-1]%mo;
	for(int i=0;i<n;i++)fi[i]=0;
}
int fl[N],gl[N];
void poly_ln(int n)
{
	for(int i=0;i<n;i++)fl[i+n]=gl[i]=gl[i+n]=0;
	int len=1;while(len<n)len<<=1;
	for(int i=0;i<len;i++)fv[i]=fl[i];poly_inv(len);
	for(int i=0;i<len;i++)fd[i]=fl[i];poly_der(len);
	for(int i=0;i<len;i++)a[i]=gv[i],b[i]=gd[i];poly_mul(len,len);
	for(int i=0;i<len;i++)fi[i]=a[i];poly_int(len);
	for(int i=0;i<n;i++)gl[i]=gi[i];
	for(int i=0;i<n;i++)gl[i+n]=fl[i]=fl[i+n]=0;
}
int fe[N],ge[N];
void poly_exp(int n)
{
	for(int i=0;i<n;i++)fe[i+n]=ge[i]=ge[i+n]=0;
	int len=1;ge[0]=1;
	while(len<n)
	{
		len<<=1;
		for(int i=0;i<len;i++)fl[i]=ge[i];poly_ln(len);
		for(int i=0;i<len;i++)a[i]=dec(fe[i],gl[i]),b[i]=ge[i];a[0]=inc(a[0],1);poly_mul(len,len);
		for(int i=0;i<len;i++)ge[i]=a[i];
	}
	for(int i=0;i<n;i++)ge[i+n]=fe[i]=fe[i+n]=0;
}
int fp[N],gp[N];
void poly_pow(int n,int k)
{
	for(int i=0;i<n;i++)fp[i+n]=gp[i]=gp[i+n]=0;
	int len=0;while(!fp[len])len++;
	int m=n-len,w=fp[len],vw=inv(w),t=ksm(w,k);
	for(int i=0;i<m;i++)fl[i]=1ll*fp[i+len]*vw%mo;poly_ln(m);
	for(int i=0;i<m;i++)fe[i]=1ll*k*gl[i]%mo;poly_exp(m);
	for(int i=0;i+1ll*k*len<(ll)n;i++)gp[i+k*len]=1ll*t*ge[i]%mo;
	for(int i=0;i<n;i++)gp[i+n]=fp[i]=fp[i+n]=0;
}
int fm1[N],fm2[N],gm1[N],gm2[N];
void poly_mod(int n,int m)
{
	for(int i=0,len=n;i<len;i++)fm1[i+len]=0;
	for(int i=0,len=m;i<len;i++)fm2[i+len]=0;
	for(int i=0,len=n-m+1;i<len;i++)gm1[i]=gm1[i+len]=0;
	for(int i=0,len=m-1;i<len;i++)gm2[i]=gm2[i+len]=0;
	
	for(int i=0;i<n-m+1;i++)fv[i]=fm2[m-1-i];poly_inv(n-m+1);
	
	for(int i=0;i<n;i++)a[i]=fm1[n-1-i];
	for(int i=0;i<n-m+1;i++)b[i]=gv[i];
	poly_mul(n,n-m+1);
	
	for(int i=0;i<n-m+1;i++)gm1[i]=a[n-m-i];
	for(int i=0;i<m;i++)a[i]=fm2[i];
	for(int i=0;i<n-m+1;i++)b[i]=gm1[i];
	poly_mul(m,n-m+1);
	
	for(int i=0;i<m;i++)gm2[i]=dec(fm1[i],a[i]); 
	
	for(int i=0,len=n;i<len;i++)fm1[i]=fm1[i+len]=0;
	for(int i=0,len=m;i<len;i++)fm2[i]=fm2[i+len]=0;
	for(int i=0,len=n-m+1;i<len;i++)gm1[i+len]=0;
	for(int i=0,len=m-1;i<len;i++)gm2[i+len]=0;	
}
struct Segment_Tree
{
	#define lson o<<1
	#define rson o<<1|1
	#define mid ((l+r)>>1)
	int size,f[M],li[N],ri[N],len[N];
	void clear(){size=0;}
	void solve(int o,int l,int r)
	{
		if(l==r)
		{
			return;
		}
		solve(lson,l,mid);
		solve(rson,mid+1,r);
		for(int i=0;i<len[lson];i++)a[i]=f[li[lson]+i];
		for(int i=0;i<len[rson];i++)b[i]=f[li[rson]+i];
		poly_mul(len[lson],len[rson]);
		len[o]=len[lson]+len[rson]-1;
		while(len[o]>1&&!a[len[o]-1])len[o]--;
		li[o]=size+1;ri[o]=size+len[o];
		for(int i=0;i<len[o];i++)f[++size]=a[i];
	}
};
int t[N],p[N],q[N],dp[N],dq[N],ddp[N],ddq[N]; 
int coefficient(int n,int len)
{
	int v=inv(2),wn=ksm(h,(mo-1)/(2*len)),wm=inv(wn); 
	
	for(int i=0;i<len;i++)dp[i]=p[i],dq[i]=q[i];
	ntt(dp,len,+1);ntt(dq,len,+1);
	while(n) 
	{
		//ddp ddq
		for(int i=0;i<len;i++)ddp[2*i]=dp[i],ddq[2*i]=dq[i];
		for(int i=0,w=1;i<len;i++,w=1ll*w*wn%mo)p[i]=1ll*p[i]*w%mo,q[i]=1ll*q[i]*w%mo;
		ntt(p,len,+1);ntt(q,len,+1);
		for(int i=0;i<len;i++)ddp[2*i+1]=p[i],ddq[2*i+1]=q[i];
		//p dp
		for(int i=0;i<2*len;i++)t[i]=1ll*ddp[i]*ddq[i^len]%mo;
		if(n&1)for(int i=0,w=1;i<2*len;i++,w=1ll*w*wm%mo)t[i]=1ll*t[i]*w%mo;
		for(int i=0;i<len;i++)t[i]=1ll*v*inc(t[i],t[i+len])%mo,dp[i]=t[i];
		ntt(t,len,-1);for(int i=0;i<len;i++)p[i]=t[i];	
		//q dq
		for(int i=0;i<2*len;i++)t[i]=1ll*ddq[i]*ddq[i^len]%mo;
		for(int i=0;i<len;i++)t[i]=1ll*v*inc(t[i],t[i+len])%mo,dq[i]=t[i];
		ntt(t,len,-1);for(int i=0;i<len;i++)q[i]=t[i];
		
		n>>=1; 
	}
	return 1ll*p[0]*inv(q[0])%mo;
}
int recurrence(int *f,int *g,int n,int k)
{
	int len=1;
	while(len<(n+1))len<<=1;
	for(int i=0;i<len;i++)p[i]=q[i]=0; 
	q[0]=1;for(int i=1;i<=n;i++)q[i]=dec(0,g[i]);
	
	for(int i=0;i<n;i++)a[i]=f[i];
	for(int i=0;i<=n;i++)b[i]=q[i];
	poly_mul(len,len); 
	for(int i=0;i<n;i++)p[i]=a[i];
	
	return coefficient(k,len);
}
struct Seq
{
	int id,dt;
	vector<int>v;
	int len(){return v.size();}
};
bool operator<(Seq a,Seq b)
{
	return a.len()-a.id<b.len()-b.id;
}
Seq R,Rw,Rn;
void BM(int *f,int n)
{
	R.id=-1;R.v.clear();
	Rw.id=-inf;Rw.v.clear();
	int pos=-1;
	for(int i=0;i<n;i++)if(f[i]){pos=i;break;}
	if(pos==-1)return;
	for(int i=0;i<n;i++,R=Rn)
	{
		R.dt=f[i];
		for(int k=0;k<R.len();k++)R.dt=dec(R.dt,1ll*R.v[k]*f[i-k-1]%mo);		
		Rn=R;Rn.id=i;
	
		if(!R.dt)continue;
		if(i<=pos)
		{
			Rn.v.clear();
			if(i==pos)Rn.v.push_back(0);
		}
		else
		{
			int len=i-Rw.id-1,t=1ll*R.dt*inv(Rw.dt)%mo;
			for(int k=Rn.len();k<len+Rw.len();k++)Rn.v.push_back(0);
			for(int k=0;k<Rw.len();k++)Rn.v[len+k]=dec(Rn.v[len+k],1ll*t*Rw.v[k]%mo);
			Rn.v[len-1]=inc(Rn.v[len-1],t);
		}
		Rw=min(Rw,R);
	}
}
